package com.yangzhe.algorithm.c034;

// 判断链表是否是回文结构
// 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/
public class Code04_PalindromeLinkedList_LeetCode {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode();
        node1.val = 1;

        ListNode node2 = new ListNode();
        node2.val = 1;

        ListNode node3 = new ListNode();
        node3.val = 2;

        ListNode node4 = new ListNode();
        node4.val = 1;

        node1.next = node2;
        //node2.next = node3;
        //node3.next = node4;

        isPalindrome(node1);
    }

    /**
     * 使用容器的方法，可以使用栈，将节点都压栈，弹出时（逆序）和原链表比较，如果每个节点值都一致则时回文结构
     * <p>
     * 如下方法可以使得额外空间复杂度O(1)
     *
     * @param head 头节点
     * @return 是否回文
     */
    public static boolean isPalindrome(ListNode head) {
        // 1. 找到链表中点
        int count = countNode(head);
        // 特殊情况，1个的情况一定是回文
        if (count == 1) {
            return true;
        }
        // 1 -> 2 -> 2' -> 1' 则中点是 2
        // 1 -> 2 -> 1‘ 则中点 是2
        ListNode midNode = getMidNode(head, count);

        // 2. 将从中点后一个节点开始 链表逆序
        // 1 -> 2 -> 2' -> 1' 逆序后 1 -> 2 <- 2' < 1'
        // 1 -> 2 -> 1‘ 逆序后 1 -> 2 <- 1'
        HeadAndEnd headAndEnd = reverse(midNode.next);
        midNode.next = null;
        headAndEnd.end.next = midNode;

        // 3. 两个指针一个从头，一个从中点后一个节点 开始遍历比对，如果每个值都一致则是回文结构
        boolean result = true;
        ListNode forwardCur = head;
        ListNode reverseCur = headAndEnd.head;
        while (reverseCur != forwardCur && reverseCur.next != null) {
            if (forwardCur.val != reverseCur.val) {
                result = false;
                break;
            }

            reverseCur = reverseCur.next;
            forwardCur = forwardCur.next;
        }

        // 4. 还原链表
        //  1 -> 2 <- 2'(e) < 1'(h) 还原为
        headAndEnd.end.next = null;
        HeadAndEnd restoreHeadAndEnd = reverse(headAndEnd.head);
        midNode.next = restoreHeadAndEnd.head;

        return result;
    }

    /**
     * 数链表节点的个数
     *
     * @param head 头节点
     * @return 链表个数
     */
    public static int countNode(ListNode head) {
        ListNode current = head;
        int result = 0;
        while (current != null) {
            result++;
            current = current.next;
        }

        return result;
    }

    /**
     * 链表中点
     *
     * @param head  头节点
     * @param count 链表个数
     * @return 链表中间节点
     */
    public static ListNode getMidNode(ListNode head, int count) {
        // 除法向上取整  x / y向上取整 = (x + y - 1) / y
        int mid = (count + 2 - 1) / 2;
        ListNode midNode = head;
        while (mid != 0) {
            midNode = head;
            head = head.next;
            mid--;
        }

        return midNode;
    }

    public static HeadAndEnd reverse(ListNode head) {
        HeadAndEnd result = new HeadAndEnd();
        result.end = head;

        ListNode pre = null;
        ListNode originNext;
        while (head != null) {
            originNext = head.next;
            head.next = pre;
            pre = head;

            head = originNext;
        }
        result.head = pre;

        return result;
    }

    public static class HeadAndEnd {
        ListNode head;
        ListNode end;
    }
}
